package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:查找第一个等于目标值的元素
 * author: Mr.Du
 * Date: 2023/5/22
 * Time: 15:38
 */
public class BinarySearch1 {

    public static void main(String[] args) {
        int[] nums = {2, 4, 5, 5, 6, 6, 8, 10, 10, 10, 10, 20, 30, 40};
        System.out.println("原数组为: " + Arrays.toString(nums));
//        nums = new int[]{1, 2, 3, 4, 5, 5, 7, 7};
        int res = firstIndexOfElementEqualToTarget(nums, 3);
        System.out.println("查找第一个等于目标值5的元素：" + res);
        res = lastIndexOfElementEqualToTarget(nums, 7);
        System.out.println("查找最后一个等于目标值7的元素：" + res);
        res = elementGreaterThanTheTargetValue11(nums, 6);
        System.out.println("查找第一个大于目标值6的元素：" + res);
        res = lastIndexOfElementLessThanTarget(nums, 6);
        System.out.println("查找最后一个小于目标值6的元素：" + res);
        res = firstIndexOfElementGreaterThanOrEqualToTarget(nums, 7);
        System.out.println("查找第一个大于等于目标值7：" + res);
         res = lastIndexOfElementLessThanOrEqualToTarget(nums, 6);
        System.out.println("查找最后一个小于等于目标值6的元素：" + res);
        nums = new int[]{5, 6, 0, 1, 2, 3};
        System.out.println("原数组为: " + Arrays.toString(nums));
        res = searchInRotatedArray(nums, 3);
        System.out.println("在旋转排序数组中查找目标值为3的索引：" + res);
        res = searchInRotatedArray(nums, 8);
        System.out.println("在旋转排序数组中查找目标值为8的索引：" + res);
        res = findMinInRotatedArray(nums);
        System.out.println("在旋转排序数组中查找最小值：" + res);
    }
    
    // 查找第一个等于目标值的元素
    public static int firstIndexOfElementEqualToTarget(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                // 说明在右半部分
                left = mid + 1;
            }else{
                // 可能找到了，但不确定是否是第一个，继续缩小范围
                right = mid - 1;
            }
        }
        if(left < nums.length && nums[left] == target){
            return left;
        }
        return -1;
    }
    
    // 查找最后一个等于目标值的元素
    public static int lastIndexOfElementEqualToTarget(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target){
                // 可能找到了，但不确定是否是最后一个，继续缩小范围
                left = mid + 1;
            }else{
                // 大于target，就缩小范围，在左半部分
                right = mid - 1;
            }
        }
        if(right >= 0 && nums[right] == target){
            return right;
        }
        return -1;
    }
    
    /**
     * 查找第一个大于目标值的元素
     * 如果中间元素小于等于目标值，说明目标值在右半部分，将左边界移动到mid + 1。如果中间元素大于目标值，说明目标值在左半部分，
     * 将右边界移动到mid - 1。循环结束后，返回左边界的索引值，即为第一个大于目标值的元素的位置。如果左边界超过数组范围，
     * 则返回-1表示未找到符合条件的元素。
     * @param nums
     * @param target
     * @return
     */
    public static int elementGreaterThanTheTargetValue11(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                // 可能找到了，但不确定是否是第一个，继续缩小范围
                right = mid - 1;
            }
        }
        return left < nums.length ? left : -1;
    }
    
    
    // 查找最后一个小于目标值的元素
    public static int lastIndexOfElementLessThanTarget(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right >= 0 ? right : -1;
    }
    
    
    
    // 查找第一个大于等于目标值的元素
    public static int firstIndexOfElementGreaterThanOrEqualToTarget(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left < nums.length ? left : -1;
    }
    
    
    // 查找最后一个小于等于目标值的元素
    public static int lastIndexOfElementLessThanOrEqualToTarget(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right >= 0 ? right : -1;
    }
    
    // 在旋转排序数组中查找目标值
    public static int searchInRotatedArray(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid; // 找到目标值
            }
            
            // 左半部分有序
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // 目标值在左半部分，更新右边界
                } else {
                    left = mid + 1; // 目标值在右半部分，更新左边界
                }
            }
            // 右半部分有序
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // 目标值在右半部分，更新左边界
                } else {
                    right = mid - 1; // 目标值在左半部分，更新右边界
                }
            }
        }
        
        return -1; // 没找到目标值
    }
    
    // 查找循环有序数组中的最小元素
    public static int findMinInRotatedArray(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                left = mid + 1; // 最小元素在右半部分
            } else {
                right = mid; // 最小元素在左半部分或当前位置
            }
        }
        
        return nums[left]; // 最小元素为nums[left]
    }

    // 查找第一个等于目标值的元素
    public int left_bound(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left < nums.length && nums[left] == target? left : -1;
    }

    // 查找最后一个等于目标值的元素
    public int right_bound(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return right >= 1 && nums[right - 1] == target? right - 1 : -1;
    }
    
    
}
